#pragma once

enum state
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K,class V>
struct hashdata
{
	pair<K, V> _kv;
	state _st = EMPTY;
};


template<class K>
struct defaultHashFunc
{
	const K& operator()(const K& key)
	{
		return key;
	}
};

template<>
struct defaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		size_t hash;
		for (auto ch : str)
		{
			hash += ch * 131;
		}
		return hash;
	}
};

template<class K, class V,class hashFunc = defaultHashFunc<K> >
class hashtable
{

public:
	hashtable()
	{
		_table.resize(10);
	}

	bool insert(const pair<K, V>& kv)
	{
		hashFunc hf;
		if (_n * 10 / _table.size() >= 7)
		{
			int newsize = _table.size() * 2;
			hashtable<K, V> newtable;
			newtable._table.resize(newsize);
			for (int i = 0; i < _table.size(); i++)
			{
				if (_table[i]._st == EXIST)
				{
					newtable.insert(_table[i]._kv);
				}
			}
			_table.swap(newtable._table);
		}

		size_t hashi = hf(kv.first) % _table.size();
		while (_table[hashi]._st != EMPTY)
		{
			hashi++;
			hashi %= _table.size();
		}
		_table[hashi]._kv = kv;
		_table[hashi]._st = EXIST;
		_n++;

		return true;
	}

	hashdata<const K, V>* find(const K& key)
	{
		hashFunc hf;
		size_t hashi = hf(key) % _table.size();
		while (_table[hashi]._st != EMPTY)
		{
			if (_table[hashi]._st == EXIST && _table[hashi]._kv.first == key)
			{
				return (hashdata<const K, V>*)&_table[hashi];
			}
			hashi++;
			hashi %= _table.size();
		}

		return nullptr;
	}

	bool erase(const K& key)
	{
		hashdata<const K, V>* ret = find(key);
		if (ret)
		{
			_n--;
			ret->_st = DELETE;
			return true;
		}
		return false;
	}



private:
	vector<hashdata<K, V>> _table;
	int _n = 0;
};

namespace hash_bucket
{



}